1. Field of the Invention
The present invention is related generally to data communication systems and, in particular, to network control of data communication systems.
2. Background Information
Data communication systems generally consist of multiple networks that are linked together with bridges, switches, routers, or other devices. These linking devices direct data packets along various paths from an origination to a destination. Since a data communication system tends to be large with many networks and interconnecting links, typically a data packet can take many paths from its origination to its destination. A goal of a network traffic director system is to direct the journey of each data packet from its origination to its destination so that the capacity of the network is efficiently utilized.
Traditional network traffic director systems utilize a plurality of network routers based on Internet Protocol (IP). The IP routing approaches are based on a Shortest Path (SP) method in which packets are sent to their destination along the shortest paths in the network. There are various methods to determine shortest paths among the IP routing approaches. However, these approaches all share a common assumption that if each packet travels along the shortest path, then the overall workload required for the routing will remain as small as possible.
The assumption of traditional routing systems would hold true if the overall performance of a routing system could be adequately measured solely on the basis of the total number of decisions that routers need to perform. However, other factors are involved in the overall performance of a routing system. One of these factors is the amount of congestion in a data communication system. Some theoretical proposals exist which attempt to address the congestion of network traffic director systems. These approaches, however, are impractical in providing adequate solutions to the congested problem. The end result of some of these approaches produces, on average, flows that are little different than the shortest path methods of IP routing taking congestion into account. Another theoretical approach to congestion is intended for environments having predefined aspects, such as loading and network topology. However, a data communication system is seldom sufficiently predictable for these predefined approaches.
Other theoretical approaches attempt to address an aspect of the stochastic (random) nature of flows in a data communication system by allowing for randomness in the arrival times of individual data packets into a linking device. These approaches, however, are still formulated in a deterministic manner by requiring that demand or load rates and flow rates in other parts of the communication system be known in advance of their actual occurrence.
These prior art deterministic approaches are not ideally suited for data communication system environments in which demands or loads and flows in other portions of the data communication system have stochastic distributions due to changing demands or loads of individual users or due to any multiplexing involved. This means that not only are the arrival times of individual packets random, but also the rates of the demands or loads and flows in other portions of the data communication system are random and not known before their actual occurrence.
An effective optimization method must not only minimize congestion in the data communication system but it must be robust enough to adapt to sudden changes in conditions of the data communication system such as packet arrival, loading on the system, and changes to the system topology, including but not limited to the insertion and removal of nodes, without predefined scenarios of when or how these changes will occur.
In data communication systems, loading changes quickly and dramatically due to such influences as changing demands or loads of individual users and multiplexing methods such as time division multiplexing (TDM) where time slots of system use are divided among individual users. With TDM, a data communication system constantly changes the particular users on the system at any given moment, thus loading changes rapidly. Network topology can also have rapid stochastic changes due to situations such as equipment failures or weather conditions.
Also, whereas the prior art systems and methods focus on a single indicator, such as shortest path or average delay, as a basis to optimize data flow, there are many additional factors. These include average queue length at various data communication system linking devices, variance or standard deviation in individual delays of data packets traveling from an origination to a destination, and average and variance of the individual utilized capacity of links and linking devices in a data communication system. Thus, a system and method is greatly desired which optimizes packet flow in a data communication system based on numerous factors while being robust enough to effectively adapt to unexpected events.